package com.leetcode.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
 * User:yxd
 * Date:2022-05-13
 * Time:17:25
 */
public class M01_05 {
    public boolean oneEditAway(String first, String second) {
        //状态定义F(i,j)表示前i个字符和前j个字符能否编辑
        //状态转移方程:如果第i- 1和第j- 1个字符相等就直接F(i,j) = F(i- 1,j- 1)
        //如果不相等就是从三个状态里面选择一个最小的F(i,j) = min(F(i- 1,j),F(i- 1,j -1),F(i,j - 1)) + 1
        //赋初值第一列第一行都是依次递增
        int[][] dp = new int[first.length() + 1][second.length() + 1];
        for(int i = 0;i <= first.length();i ++){
            dp[i][0] = i;
        }
        for(int i = 0;i <= second.length();i ++){
            dp[0][i] = i;
        }
        for(int i = 1;i <= first.length();i ++){
            for(int j = 1;j <= second.length();j ++){
                if(first.charAt(i - 1) == second.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    int a = Math.min(dp[i - 1][j],dp[i][j - 1]);
                    dp[i][j] = Math.min(dp[i - 1][j - 1],a) + 1;
                }
            }
        }
        if(dp[first.length()][second.length()] <= 1){
            return true;
        }else{
            return false;
        }
    }
}
